Was ist der graf?
Der Graph, auch bekannt als Diagramm, ist ein abstraktes mathematisches Konzept, das zur Darstellung von Beziehungen zwischen Objekten verwendet wird. Ein Graph besteht aus Knoten (oder Ecken), die Objekte repräsentieren, und Kanten, die Verbindungen oder Beziehungen zwischen diesen Objekten darstellen.
- Knoten (Ecken): Die grundlegenden Bausteine eines Graphen. Sie repräsentieren Entitäten oder Objekte. (siehe: https://de.wikiwhat.page/kavramlar/Knoten%20(Graphentheorie))
- Kanten: Verbinden Paare von Knoten und repräsentieren die Beziehungen zwischen ihnen. Kanten können gerichtet (in diesem Fall spricht man von einem gerichteten Graphen oder Digraphen) oder ungerichtet sein. (siehe: https://de.wikiwhat.page/kavramlar/Kante%20(Graphentheorie))
- Gerichtete Graphen (Digraphen): Graphen, bei denen die Kanten eine Richtung haben. Die Beziehung zwischen zwei Knoten ist in diesem Fall nicht notwendigerweise symmetrisch. (siehe: https://de.wikiwhat.page/kavramlar/Gerichteter%20Graph)
- Ungerichtete Graphen: Graphen, bei denen die Kanten keine Richtung haben. Die Beziehung zwischen zwei Knoten ist symmetrisch.
- Gewichtete Graphen: Graphen, bei denen jeder Kante ein Gewicht zugeordnet ist, das beispielsweise die Kosten, die Entfernung oder die Kapazität der Verbindung repräsentieren kann.
- Adjazenzmatrix/Adjazenzliste: Datenstrukturen zur Repräsentation von Graphen im Computer. Die Adjazenzmatrix speichert eine Matrix, in der die Zeilen und Spalten die Knoten repräsentieren und der Eintrag (i, j) angibt, ob es eine Kante zwischen Knoten i und j gibt. Die Adjazenzliste speichert für jeden Knoten eine Liste der benachbarten Knoten.
Graphen finden Anwendung in vielen Bereichen, wie z.B. in sozialen Netzwerken, Routenplanung, Logistik, Informatik (z.B. Compilerbau, Datenbanken), Biologie (z.B. Proteininteraktionsnetzwerke) und vielen mehr. Es gibt viele Algorithmen zur Analyse und Bearbeitung von Graphen, wie z.B. https://de.wikiwhat.page/kavramlar/Breitensuche, https://de.wikiwhat.page/kavramlar/Tiefensuche, Dijkstra's Algorithmus (zur Bestimmung des kürzesten Pfades) und viele mehr.